﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace SortSearch
{
    class DutchNationalFlagProblem
    {
        //problem description: one sort, red on one side, blue on the other, white in the middle
        public void ThreeWayPartition(int[] arr, int n)
        {
            int p = -1;
            int q = n;
            int i = 0;

            while (i < q)
            {
                if (arr[i] == 1)
                {
                    p++;
                    swap(ref arr[i], ref arr[p]);
                    i++;
                }
                else if (arr[i] == 2)
                {
                    q--;
                    swap(ref arr[i], ref arr[q]);
                }
                else
                {
                    i++;
                }
            }
        }

        private void swap(ref int i, ref int j)
        {
            int temp = i;
            i = j;
            j = temp;
        }

        static void Main(string[] args)
        {
            int[] arr = { 1, 0, 2, 0, 1, 2, 1, 1, 2 };


        }
    }
}
